package com.kehao.leetcode.middle.other;

import org.junit.Test;

import java.util.*;

public class LeastIntervalSolution {
    public int leastInterval(char[] tasks, int n) {
        List<Character> list = new ArrayList<>();
        HashMap<Character,Integer> countMap = new HashMap<>();
        for (int i = 0; i < tasks.length; i++) {
            if(countMap.containsKey(tasks[i])){
                countMap.put(tasks[i],countMap.get(tasks[i])+1);
            }else {
                countMap.put(tasks[i],1);
            }
        }
        countMap.put('-',0);
        int pos = 0;
        while (countMap.size()>1){
            char candidate = '-';
            Set coolingSet = getCoolingSet(list,pos,n);
            for (char c:countMap.keySet()){
                if(coolingSet.contains(c)) continue;
                if(countMap.get(c)>countMap.get(candidate)){
                    candidate = c;
                }
            }
            if(candidate!='-') {
                int count = countMap.get(candidate);
                if(count==1) {
                    countMap.remove(candidate);
                }else {
                    countMap.put(candidate,count-1);
                }
            }
            list.add(candidate);
            pos++;
        }
        return list.size();
    }

    private Set getCoolingSet(List<Character> list, int pos, int n) {
        HashSet set = new HashSet();
        for (int i = pos-n; i < pos; i++) {
            if(i>=0) set.add(list.get(i));
        }
        return set;
    }

    @Test
    public void test01(){
        System.out.println(leastInterval(new char[]{'A', 'A', 'A', 'B', 'B', 'B'}, 2));
    }

    @Test
    public void test02(){
        System.out.println(leastInterval(new char[]{'A','A','A','B','B','B'}, 0));
    }

    @Test
    public void test03(){
        System.out.println(leastInterval(new char[]{'A','A','A','A','A','A','B','C','D','E','F','G'}, 2));
    }

    @Test
    public void test04(){
        System.out.println(leastInterval(new char[]{'A','A','A','B','B','B', 'C','C','C', 'D', 'D', 'E'}, 2));
    }
}
